package com.lee.algorithm.sort.quick;

import static com.lee.algorithm.sort.SortUtil.print;
import static com.lee.algorithm.sort.SortUtil.swap;

/***
 * @description 快排，逐步优化实现
 * @author 青石路
 * @date 2022/3/13 22:47
 */
public class OneByOne {

    public static void main(String[] args) {
        int[] arr = new int[]{9,8,3,2,6,4,5,0,1,1,1};
        //int[] arr = new int[]{9,8,4,2,3,4,4,5,2,6,4};
        quickSort(arr);
        print(arr);
    }

    public static void quickSort(int[] arr){
        if (arr == null || arr.length < 2) {
            return;
        }
        // quickSort1(arr, 0, arr.length - 1);
        //quickSort2(arr,0,arr.length-1);
        quickSort3(arr,0,arr.length-1);
    }

    /**
     * 快排1.0
     *      基于两区域划分，一次处理一个元素
     * @param arr
     * @param left
     * @param right
     * @author 博客园 @ 青石路
     */
    public static void quickSort1(int[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

        int lte = left - 1;

        /**
         * arr[right] 作为 target，arr[left ~ right-1] 做两区域划分
         */
        for(int i=left; i<right; i++) {
            if (arr[i] <= arr[right]) {
                // ++lte，既用于取左边界的下一个元素，也实现了右移
                swap(arr, ++lte, i);
            }
        }

        // target 与大于区的第一个元素进行交换
        swap(arr, lte+1, right);

        // 交换完之后，target 的位置是 lte+1，lte+1 位置上的元素无需在动

        // 小于等于区域继续进行划分
        quickSort1(arr, left, lte);

        // 大于区域继续进行划分
        quickSort1(arr, lte+2, right);
    }

    /**
     * 快排2.0
     *      基于荷兰国旗问题，一次处理一批相同的元素
     * @param arr
     * @param left
     * @param right
     * @author 博客园 @ 青石路
     */
    public static void quickSort2(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }

        // lt：左边界索引，gt：右边界索引
        int lt = left-1, gt = right, i=left;

        /**
         * arr[right] 作为 target，arr[left ~ right-1] 做荷兰国旗处理
         */
        while(i < gt) {
            if (arr[i] < arr[right]) {
                // arr[i] 和 lt 后一个元素进行交换， lt右移，i++
                swap(arr, ++lt, i++);
            } else if (arr[i] > arr[right]) {
                // arr[i] 和 gt 前一个元素进行交换， gt 左移，i 不动
                swap(arr, --gt, i);
            } else {
                // arr[i] 等于 target，i++
                i++;
            }
        }

        // 大于区的第一个元素与 target 进行交换
        swap(arr, gt, right);

        // 小于区域继续进行划分
        quickSort2(arr,left,lt);

        // 大于区域继续进行划分
        quickSort2(arr, gt+1, right);
    }

    /**
     * 快排3.0
     *      基于荷兰国旗问题，一次处理一批相同的元素
     *      随机取 target
     * @param arr
     * @param left
     * @param right
     * @author 博客园 @ 青石路
     */
    public static void quickSort3(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }

        /**
         * 将 left 至 right 之间的随机位置上的一个数与 arr[right] 进行交换
         * 那么 arr[right] 即是 arr[left] ~ arr[right] 之间的随机某个数
         * 交换完之后，以 arr[right] 作为 target，进行荷兰国旗问题处理
         */
        swap(arr, left + (int) (Math.random() * (right-left+1)), right);

        // lt：左边界索引，gt：右边界索引
        int lt = left-1, gt = right, i=left;

        /**
         * arr[right] 作为 target，arr[left ~ right-1] 做荷兰国旗处理
         */
        while(i < gt) {
            if (arr[i] < arr[right]) {
                // arr[i] 和 lt 后一个元素进行交换， lt右移，i++
                swap(arr, ++lt, i++);
            } else if (arr[i] > arr[right]) {
                // arr[i] 和 gt 前一个元素进行交换， gt 左移，i 不动
                swap(arr, --gt, i);
            } else {
                // arr[i] 等于 target，i++
                i++;
            }
        }

        // 大于区的第一个元素与 target 进行交换
        swap(arr, gt, right);

        // 小于区域继续进行划分
        quickSort2(arr,left,lt);

        // 大于区域继续进行划分
        quickSort2(arr, gt+1, right);
    }
}
